﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace IOP.Algorithm.Sort
{
    public static class QuickSortExtension
    {
        /// <summary>
        /// 快速排序
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TKey"></typeparam>
        /// <param name="sources"></param>
        /// <param name="compareKey"></param>
        /// <returns></returns>
        public static void QuickSort<TSource, TKey>(this IList<TSource> sources, Func<TSource, TKey> compareKey, SortOrder order = SortOrder.ASC)
            where TKey : IComparable<TKey>
        {
            SortFunction(sources, compareKey, 0, sources.Count() - 1, order);
        }

        /// <summary>
        /// 排序函数
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TKey"></typeparam>
        /// <param name="sources"></param>
        /// <param name="compareKey"></param>
        /// <param name="lowIndex"></param>
        /// <param name="heightIndex"></param>
        private static void SortFunction<TSource, TKey>(IList<TSource> sources, Func<TSource, TKey> compareKey, int lowIndex, int heightIndex, SortOrder order)
            where TKey : IComparable<TKey>
        {
            if (lowIndex >= heightIndex) return;
            int middlewareIndex = Partition(sources, compareKey, lowIndex, heightIndex, order);
            SortFunction(sources, compareKey, lowIndex, middlewareIndex, order);
            SortFunction(sources, compareKey, middlewareIndex + 1, heightIndex, order);
        }

        /// <summary>
        /// 中位数函数
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TKey"></typeparam>
        /// <param name="sources"></param>
        /// <param name="compareKey"></param>
        /// <param name="leftIndex"></param>
        /// <param name="rightIndex"></param>
        /// <returns></returns>
        private static int Partition<TSource, TKey>(IList<TSource> sources, Func<TSource, TKey> compareKey, int leftIndex, int rightIndex, SortOrder order)
            where TKey : IComparable<TKey>
        {
            int i = leftIndex;
            int j = rightIndex;
            TKey keyValue = compareKey(sources[leftIndex]);
            TSource keySource = sources[leftIndex];
            while (i < j)
            {
                switch (order)
                {
                    case SortOrder.ASC:
                        while (i < j && (compareKey(sources[j]).CompareTo(keyValue) == 1 || compareKey(sources[j]).CompareTo(keyValue) == 0)) j--;
                        sources[i] = sources[j];
                        while (i < j && (compareKey(sources[i]).CompareTo(keyValue) == -1 || compareKey(sources[i]).CompareTo(keyValue) == 0)) i++;
                        sources[j] = sources[i];
                        break;
                    case SortOrder.DESC:
                        while (i < j && (compareKey(sources[j]).CompareTo(keyValue) == -1 || compareKey(sources[j]).CompareTo(keyValue) == 0)) j--;
                        sources[i] = sources[j];
                        while (i < j && (compareKey(sources[i]).CompareTo(keyValue) == 1 || compareKey(sources[i]).CompareTo(keyValue) == 0)) i++;
                        sources[j] = sources[i];
                        break;
                }
            }
            sources[i] = keySource;
            return i;
        }
    }
}
